#include <iostream>
#include <vector>

using namespace std;

/**
 * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据
 * 每个孩子的表现，预先给他们评分。要求:
 *      每个孩子至少分配到 1 个糖果。
 *      评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
 */
class Solution {
public:
    /**
     * 我的解法：从左向右遍历，遇到上升区间递增发糖，遇到下降区间不断
     * 跳过，直到下降区间结束，回头逆序发糖。边界检测：
     *      遍历结束后仍存在逆序状态，需要追加逆序发糖；
     *      交汇处取最大值。
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    int candy(vector<int>& ratings) {
        int n = ratings.size(), rev = -1, sum = 0;
        vector<int> candies(n);
        candies[0] = 1;
        bool reverse = false;
        for (int i=1; i<n; ++i) {
            if ((ratings[i-1] <= ratings[i]) && reverse) {  // 逆序结束，需要逆转更新
                candies[i-1] = 1;    // 最小值记为 1 即可
                for (int j=i-2; j>=rev; --j) candies[j] = candies[j+1] + 1;     // 逆序发糖
                candies[rev-1] = max(candies[rev-1], candies[rev]+1);           // 交汇处取最大值
                candies[i] = ratings[i-1] < ratings[i] ? candies[i-1] + 1 : 1;  // 更新自己
                reverse = false;     // 移除逆转状态
            } else if (ratings[i-1] < ratings[i]) {
                candies[i] = candies[i-1] + 1;
            } else if (ratings[i-1] == ratings[i]) {
                candies[i] = 1;
            } else {                 // ratings[i-1] > ratings[i]
                if (!reverse) {      // 首次出现逆序
                    reverse = true;  // 设置逆转状态
                    rev = i;         // 记录逆序首次出现的下标
                }                    // 否则，已经处于逆序中，什么也不用做
            }
        }
        if (reverse) {               // 遍历结束后还存在逆序状态，需要再次更新
            for (int i=n-1; i>=rev; --i) candies[i] = n-i;
            candies[rev-1] = max(candies[rev-1], n-rev+1);  // 交汇处
        }
        for (int i=0; i<n; ++i) sum += candies[i];
        return sum;
    }

    /**
     * 根据答案改进：
     * 从左到右枚举每一个同学，记前一个同学分得的糖果数量为 pre
     * 如果在最近的递增序列中，直接分配 pre+1 
     * 否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，
     * 并把该同学所在的递减序列中所有的同学都再多分配一个糖果，并且：
     *      无需显式地额外分配糖果，只需要记录当前的递减序列长度，
     *      即可知道需要额外分配的糖果数量。
     *      注意当当前的递减序列长度和上一个递增序列等长时，需要把
     *      最近的递增序列的最后一个同学也并进递减序列中。
     * 只要记录：
     *      当前递减序列长度 dec
     *      最近递增序列长度 inc
     *      前一个发糖的数量 pre
     */
    int candyBetter(vector<int>& ratings) {
        int n = ratings.size();
        int ret = 1, inc = 1, dec = 0, pre = 1;  // 第一位先发一个糖
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i-1]) {
                dec = 0;
                pre = ratings[i] == ratings[i-1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) dec++;  // 多发一颗
                ret += dec;
                pre = 1;  // 隐式发糖
            }
        }
        return ret;
    }
};
